package com.wcj.sort;

import java.util.ArrayList;

public class 基数排序{

    public static void main(String[] args) {
        String [] arr = new String[]{"23","12","36","451","2","89","78","54"};
        radixSort(arr,3);

        for (String s : arr) {
            System.out.println(s);
        }
    }


    public static void radixSort(String[] arr, int maxLen){
        final int BUCKETS = 256;
        ArrayList<String>[] wordsByLength = new ArrayList[maxLen + 1];
        ArrayList<String>[] bucket = new ArrayList[BUCKETS];
        for (int i = 0; i < wordsByLength.length; i++){
            wordsByLength[i] = new ArrayList<>();
        }
        for (int i = 0; i < BUCKETS;i++){
            bucket[i] = new ArrayList<>();
        }

        for (String s : arr) {
            wordsByLength[s.length()].add(s);
        }
        int idx = 0;
        for (ArrayList<String> wordList : wordsByLength) {
            for (String s : wordList) {
                arr[idx++] = s;
            }
        }
        int startingIndex = arr.length;
        for (int pos = maxLen - 1; pos >= 0; pos--){
            startingIndex -= wordsByLength[pos + 1].size();
            for (int i = startingIndex; i < arr.length; i++){
                bucket[arr[i].charAt(pos)].add(arr[i]);
            }
            idx = startingIndex;
            for (ArrayList<String> thisBucket : bucket) {
                for (String s : thisBucket) {
                    arr[idx++] = s;
                }
                thisBucket.clear();
            }
        }
    }


}
